// 给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，
// 每步可以删除任意一个字符串中的一个字符。
// 示例：
// 输入: "sea", "eat"
// 输出: 2
// 解释: 第一步将"sea"变为"ea"，第二步将"eat"变为"ea"

// 和不同的子序列相比，两个字符串都可以删除了
// 五部曲
// 1. 确定dp数组含义，`dp[i][j]`以i-1结尾的字符串word1和以j-1结尾的字符串word2，想到达到相等，需要删除元素的最少次数
// 2. 确定递推公式
//     1. 当`word1[i-1] === word2[j-1]`, `dp[i][j] = dp[i-1][j-1]`
//     2. 当`word1[i-1] !== word2[j-1]`,
//         1. 删除`word1[i-1]`, `dp[i-1][j] + 1`
//         2. 删除`word2[j-1]`, `dp[i][j-1] + 1`
//         3. 同时删除`word1[i-1]`和`word2[j-1]`，`dp[i-1][j-1] + 2`
//         4. `dp[i][j] = Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 2)`
// 3. dp数组初始化

function minDistance(word1, word2) {
    let dp = new Array(word1.length + 1).fill(0).map(_ => new Array(word2.length + 1).fill(0))
    for (let i = 0; i <= word1.length; i++) {
        dp[i][0] = i        
    }
    for (let j = 0; j < word2.length; j++) {
        dp[0][j] = j        
    }
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                // dp[i][j] = Math.min(dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1) 
                // dp[i][j-1] 本来就不考虑 word2[j - 1]了，那么我在删 word1[i - 1]，是不是就达到两个元素都删除的效果，即 dp[i][j-1] + 1。
                dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)  // 可简化
            }
        }        
    }
    return dp[word1.length][word2.length]
}

console.log(minDistance("sea", "eat"))

// 思路2， 只要求出两个字符的最长公共子序列长度即可，然后用两个字符串的总长度减去两个最长公共子序列的长度即可
// 时间复杂度: O(n * m)
// 空间复杂度: O(n * m)

function minDistance2(word1, word2) {
    let dp = new Array(word1.length + 1).fill(0).map(_ => new Array(word2.length + 1).fill(0))
    for (let i = 1; i <= word1.length; i++) {
        for (let j = 1; j <= word2.length; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1
            } else {
                dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1])
            }
        }        
    }
    return word1.length + word2.length  - 2 * dp[word1.length][word2.length]
}
console.log(minDistance2("sea", "eat"))